import java.util.Random;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 12:45
 **/

public class QuickSort {

    private QuickSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            //arr[l.....p - 1] < v;  arr[p + 1.....r] > v
            int p = partition(arr, l, r);
            sort(arr, l, p - 1);
            sort(arr, p + 1, r);
        }
    }
    // 将整个数组划分为两部分，大于arr[j] 放在arr[j] 后面，小于的放到前面
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r){
        int p = l + (new Random().nextInt(r - l + 1));
        swap(arr, l, p);
        // arr[l+1.....j] < v;  arr[j+1.....i] > v
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0){
                j ++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }
    private static <E> void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] arr =  ArrayGenerator.generatorRandomArray(n, n);
        SortingHelper.sortTest("QuickSort", arr);
    }

}
